给定一张带边权的弦图,给定起点终点,求这两点之间不是割集的最短路径的长度。
部分分:所有边权为
求出任意一条最短路,如果它合法就输出它的长度,否则输出 。正确性证明:
显然最短路合法就输出一定是正确的。如果最短路不合法,我们找到它的最小的、是割集的子集。由于这是最小割集,它一定把原图分成了恰好两个连通块,而且其中每一条边都横跨了两个连通块。那么有以下几种情况:
-
这个割集的大小为 ,那么其中唯一的一条边就是原图的割边,起点到终点的任意一条路径都要经过它,于是无解。
-
这个割集的大小大于 ,且它不连通。我们随便找出其中两条不相邻的边来看,假设这两条边分别是 和 ,它大概像这样:(图片来自 matthew99 的官方题解 PPT)

假设 和 分别是删掉割集后, 到 和 到 的经过的最短路径。那么 是一个长度至少为 的环,这个环上应该有弦,但是不管怎么加弦,要么与割集两边不连通矛盾,要么与 和 是最短路径矛盾。
- 这个割集的大小大于 ,且它连通。和刚才相反,我们随便找出其中两条相邻的边来看。设这两条边是 和 ,它大概像这样:

如果 之间没有直接连边,假设它们删掉割集后的最短路径是 。那么 是一个长度至少为 的环,和上面类似,不管怎么加弦都要矛盾。我们只能加 这条弦。但是如果 之间有直接连边,这又和一开始我们找的是最短路矛盾。
综上所述,如果最短路是割集,一定是上面的第一种情况,输出 一定是正确的。部分分做法到此结束。
正解
它永远地咕咕了。